package sort;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-11 00:12
 **/
public class HeapSort {

    public static void main(String[] args) {

        int[] arr = {9,8,7,6,5,4,3,2,1};
        sort(arr, arr.length);
        System.out.println("升序排列:" + Arrays.toString(arr));
        sort2(arr, arr.length);
        System.out.println("降序排列:" + Arrays.toString(arr));
    }

    //升序
    static void sort(int[] nums, int heapSize) {
        //原地建堆
        buildMaxHeap(nums, heapSize);

        while (heapSize > 1) {
            //交换堆顶元素和尾部元素
            swap(nums, 0, --heapSize);

            //对0位置进行siftDown(恢复堆的性质)
            maxHeapify(nums, 0, heapSize);
        }
    }

    //降序
    static void sort2(int[] nums, int heapSize) {
        //原地建堆
        buildMinHeap(nums, heapSize);

        while (heapSize > 1) {
            //交换堆顶元素和尾部元素
            swap(nums, 0, --heapSize);

            //对0位置进行siftDown(恢复堆的性质)
            minHeapify(nums, 0, heapSize);
        }
    }
    /**
     * 原地建大顶堆
     * @param a
     * @param heapSize
     */
    static void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }

    /**
     * 原地建小顶堆
     * @param a
     * @param heapSize
     */
    static void buildMinHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            minHeapify(a, i, heapSize);
        }
    }

    /**
     * 小值上浮
     * @param a
     * @param i
     * @param heapSize
     */
    static void minHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, smallest = i;
        if (l < heapSize && a[l] < a[smallest]) {
            smallest = l;
        }
        if (r < heapSize && a[r] < a[smallest]) {
            smallest = r;
        }
        if (smallest != i) {
            swap(a, i, smallest);
            minHeapify(a, smallest, heapSize);
        }
    }

    /**
     * 大值上浮
     * @param a
     * @param i
     * @param heapSize
     */
    static void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
